package com.aikon.wht.paoshan.alg;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * <pre>
 * 二叉树的构造方法：1.基于链表 2.基于数组
 * </pre>
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfTree {


    public static class BalancedBinarySearchTree<T extends Comparable<T>> extends BinarySearchTree<T> {



    }



    /**
     * 二叉搜索数
     *
     * @param <T>
     */
    public static class BinarySearchTree<T extends Comparable<T>> {

        private TreeNode<T> head;

        /**
         * 构建二叉搜索数.
         *
         * @param values
         * @param <T>
         * @return
         */
        public static <T extends Comparable<T>> BinarySearchTree build(List<T> values) {
            if (values == null) {
                return null;
            }
            BinarySearchTree<T> binarySearchTree = new BinarySearchTree();
            values.stream().forEach(i -> binarySearchTree.add(i));
            return binarySearchTree;
        }

        public void add(T val) {
            if (head == null) {
                head = new TreeNode<>(val);
                return;
            }
            TreeNode<T> currentNode = head;
            while (currentNode != null) {
                if (val.compareTo(currentNode.getVal()) < 0) {
                    if (currentNode.getLeftNode() != null) {
                        currentNode = currentNode.getLeftNode();
                    } else {
                        currentNode.setLeftNode(new TreeNode<>(val));
                        return;
                    }
                } else {
                    if (currentNode.getRightNode() != null) {
                        currentNode = currentNode.getRightNode();
                    } else {
                        currentNode.setRightNode(new TreeNode<>(val));
                        return;
                    }
                }
            }
        }

        public TreeNode<T> find(T val) {
            if (val == null || head == null) {
                return null;
            }
            TreeNode<T> currentNode = head;
            while (currentNode != null && !val.equals(currentNode.getVal())) {
                if (val.compareTo(currentNode.getVal()) < 0) {
                    currentNode = currentNode.getLeftNode();
                } else {
                    currentNode = currentNode.getRightNode();
                }
            }
            if (currentNode == null) {
                return null;
            }
            return currentNode;
        }

        public void delete(T val) {
            if (val == null) {
                return;
            }
            TreeNode<T> currentNode = head;
            TreeNode<T> parentNode = null;
            while (!val.equals(currentNode.getVal()) && currentNode != null) {
                if (val.compareTo(currentNode.getVal()) < 0) {
                    parentNode = currentNode;
                    currentNode = currentNode.getLeftNode();
                } else {
                    parentNode = currentNode;
                    currentNode = currentNode.getRightNode();
                }
            }
            if (currentNode == null) {
                return;
            }
            // 没有子节点
            if (currentNode.getLeftNode() == null && currentNode.getRightNode() == null) {
                if (parentNode.getRightNode() != null && val.equals(parentNode.getRightNode().getVal())) {
                    parentNode.setRightNode(null);
                } else {
                    parentNode.setLeftNode(null);
                }
            }
            // 只有右节点
            if (currentNode.getLeftNode() == null) {
                if (parentNode.getRightNode() != null && val.equals(parentNode.getRightNode().getVal())) {
                    parentNode.setRightNode(currentNode.getRightNode());
                } else {
                    parentNode.setLeftNode(currentNode.getRightNode());
                }
            }
            // 只有左节点
            if (currentNode.getRightNode() == null) {
                if (parentNode.getRightNode() != null && val.equals(parentNode.getRightNode().getVal())) {
                    parentNode.setRightNode(currentNode.getLeftNode());
                } else {
                    parentNode.setLeftNode(currentNode.getLeftNode());
                }
            }
            // 左右子节点都有
            if (currentNode.getLeftNode() != null && currentNode.getRightNode() != null) {
                if (currentNode.getLeftNode().getRightNode() == null) {
                    if (parentNode.getRightNode() != null && val.equals(parentNode.getRightNode().getVal())) {
                        parentNode.setRightNode(currentNode.getLeftNode());
                    } else {
                        parentNode.setLeftNode(currentNode.getLeftNode());
                    }
                } else {
                    TreeNode<T> p = currentNode.getLeftNode().getRightNode();
                    TreeNode<T> pp = currentNode.getLeftNode();
                    while (p.getRightNode() != null) {
                        pp = p;
                        p = p.getRightNode();
                    }
                    currentNode.setVal(p.getVal());
                    if (p.getLeftNode() != null) {
                        pp.setRightNode(p.getLeftNode());
                    } else {
                        pp.setRightNode(null);
                    }
                }
            }


        }




        /**
         * 前序遍历 中-左-右
         *
         * @return
         */
        public List<T> preOrder() {
            List<T> nodes = Lists.newArrayList();
            setPreOrderList(head, nodes);
            return nodes;
        }


        private void setPreOrderList(TreeNode<T> node, List<T> nodeValues) {
            if (node == null) {
                return;
            }
            nodeValues.add(node.getVal());
            if (node.getLeftNode() != null) {
                setPreOrderList(node.getLeftNode(), nodeValues);
            }
            if (node.getRightNode() != null) {
                setPreOrderList(node.getRightNode(), nodeValues);
            }
        }

        /**
         * 中序遍历 左-中-右
         *
         * @return
         */
        public List<T> midOrder() {
            List<T> nodeValues = Lists.newArrayList();
            setMidOrderList(head, nodeValues);
            return nodeValues;
        }

        private void setMidOrderList(TreeNode<T> node, List<T> nodeValues) {
            if (node == null) {
                return;
            }
            if (node.getLeftNode() != null) {
                setMidOrderList(node.getLeftNode(), nodeValues);
            }
            nodeValues.add(node.getVal());
            if (node.getRightNode() != null) {
                setMidOrderList(node.getRightNode(), nodeValues);
            }
        }

        /**
         * 后序遍历 左-右-中
         *
         * @return
         */
        public List<T> postOrder() {
            List<T> nodeValues = Lists.newArrayList();
            setPostOrderList(head, nodeValues);
            return nodeValues;
        }

        private void setPostOrderList(TreeNode<T> node, List<T> nodeValues) {
            if (node == null) {
                return;
            }
            if (node.getLeftNode() != null) {
                setPostOrderList(node.getLeftNode(), nodeValues);
            }
            if (node.getRightNode() != null) {
                setPostOrderList(node.getRightNode(), nodeValues);
            }
            nodeValues.add(node.getVal());
        }

        /**
         * 添加节点
         *
         * @param val
         */
        public void addRecursive(T val) {
            if (head == null) {
                head = new TreeNode<>();
            }
            addRecursive(val, head, null);
        }

        private void addRecursive(T val, TreeNode<T> treeNode, TreeNode<T> parentNode) {
            if (treeNode.getVal() == null) {
                treeNode.setVal(val);
                treeNode.setParentNode(parentNode);
                return;
            }
            if (val.compareTo(treeNode.getVal()) <= 0) {
                if (treeNode.getLeftNode() == null) {
                    treeNode.setLeftNode(new TreeNode<>());
                }
                addRecursive(val, treeNode.getLeftNode(), treeNode);
            } else {
                if (treeNode.getRightNode() == null) {
                    treeNode.setRightNode(new TreeNode<>());
                }
                addRecursive(val, treeNode.getRightNode(), treeNode);
            }
        }

        /**
         * 查找节点
         *
         * @param val
         * @return
         */
        public TreeNode<T> findRecursive(T val) {
            if (val == null) {
                return null;
            }
            return findRecursive(val, head);
        }

        private TreeNode<T> findRecursive(T val, TreeNode<T> node) {
            if (node == null) {
                return null;
            }
            if (val.compareTo(node.getVal()) < 0) {
                return findRecursive(val, node.getLeftNode());
            } else if (val.compareTo(node.getVal()) > 0) {
                return findRecursive(val, node.getRightNode());
            } else {
                return node;
            }
        }

        /**
         * 删除节点
         *
         * @param val
         * @return
         */
        public boolean deleteRecursive(T val) {
            if (val == null) {
                return false;
            }
            if (head.getVal() == null) {
                return false;
            }
            return deleteRecursive(val, head, false);
        }

        private boolean deleteRecursive(T val, TreeNode<T> node, boolean isFromLeft) {
            if (node == null) {
                return false;
            }
            if (val.compareTo(node.getVal()) < 0) {
                return deleteRecursive(val, node.getLeftNode(), true);
            } else if (val.compareTo(node.getVal()) > 0) {
                return deleteRecursive(val, node.getRightNode(), false);
            } else {
                if (node.getRightNode() == null
                        && node.getLeftNode() == null) {
                    // 没有子节点，直接删除
                    if (isFromLeft) {
                        node.getParentNode().setLeftNode(null);
                    } else {
                        node.getParentNode().setRightNode(null);
                    }
                    return true;
                }
                if (node.getLeftNode() == null) {
                    // 没有左子节点，右子节点接续到父节点
                    if (isFromLeft) {
                        node.getParentNode().setLeftNode(node.getRightNode());
                    } else {
                        node.getParentNode().setRightNode(node.getRightNode());
                    }
                    return true;
                }
                if (node.getRightNode() == null) {
                    // 没有右子节点，左子节点接续到父节点
                    if (isFromLeft) {
                        node.getParentNode().setLeftNode(node.getLeftNode());
                    } else {
                        node.getParentNode().setRightNode(node.getLeftNode());
                    }
                    return true;
                }
                if (node.getRightNode() != null && node.getLeftNode() != null) {
                    // 有两个子节点
                    // 左子节点没有右子节点则左子节点接续到父节点
                    // 左子节点有右子节点，则找出最右子节点，删除并把值赋予当前节点
                    if (isFromLeft) {
                        if (node.getLeftNode().getRightNode() == null) {
                            node.getParentNode().setLeftNode(node.getLeftNode());
                        } else {
                            node.setVal(getMaxRightNodeVal(node.getLeftNode().getRightNode()));
                        }
                    } else {
                        if (node.getLeftNode().getRightNode() == null) {
                            node.getParentNode().setRightNode(node.getLeftNode());
                        } else {
                            node.setVal(getMaxRightNodeVal(node.getLeftNode().getRightNode()));
                        }
                    }
                }
            }
            return false;
        }

        private T getMaxRightNodeVal(TreeNode<T> node) {
            if (node.getRightNode() == null) {
                T val = node.getVal();
                if (node.getLeftNode() != null) {
                    node.getParentNode().setRightNode(node.getLeftNode());
                } else {
                    node.getParentNode().setRightNode(null);
                }
                return val;
            }
            return getMaxRightNodeVal(node.getRightNode());
        }






        public static void main(String[] args) {
            BinarySearchTree binarySearchTree = BinarySearchTree.build(Lists.newArrayList(8, 4, 5, 1, 6, 7, 3, 2, 10, 9));
            System.out.println("前序：");
            binarySearchTree.preOrder().stream().forEach(System.out::println);
            System.out.println("中序：");
            binarySearchTree.midOrder().stream().forEach(System.out::println);
            System.out.println("后序：");
            binarySearchTree.postOrder().stream().forEach(System.out::println);
            System.out.println("查找：");
            TreeNode node = binarySearchTree.find(1);
            System.out.println("删除：");
            binarySearchTree.delete(4);
            System.out.println(binarySearchTree);
        }

        public static class TreeNode<T extends Comparable<T>> {

            private TreeNode<T> parentNode;

            private T val;

            private TreeNode<T> leftNode;

            private TreeNode<T> rightNode;

            public TreeNode(T val) {
                this.val = val;
            }

            public TreeNode() {
            }

            public TreeNode<T> getParentNode() {
                return parentNode;
            }

            public void setParentNode(TreeNode<T> parentNode) {
                this.parentNode = parentNode;
            }

            public T getVal() {
                return val;
            }

            public void setVal(T val) {
                this.val = val;
            }

            public TreeNode<T> getLeftNode() {
                return leftNode;
            }

            public void setLeftNode(TreeNode<T> leftNode) {
                this.leftNode = leftNode;
            }

            public TreeNode<T> getRightNode() {
                return rightNode;
            }

            public void setRightNode(TreeNode<T> rightNode) {
                this.rightNode = rightNode;
            }
        }
    }


}
